package LeetCode._02算法基础.day05滑动窗口;

import org.junit.Test;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 15 - 16:54
 * @Description 给定一个正整数数组 nums和整数 k 。
 * 请找出该数组内乘积小于 k 的连续的子数组的个数。
 * @Version 中等
 */
public class _713乘积小于k的子数组 {
    static int[] nums = {10, 5, 2, 6};
    static int[] nums1 = {10,9,10,4,3,8,3,3,6,2,10,10,9,3};
    static int k = 100;
    static int k1 = 19;

    @Test
    public void solve() {
        int res = numSubarrayProductLessThanK(nums1, k1);
        System.out.println(res);
    }
    /*by me 数太多会溢出*/
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int res = 0;
        long product;
        for (int L = 1; L <= nums.length; L++) {
            product = 1;
            for (int i = 0; i < L; i++) {
                product *= nums[i];
            }
            if (product < k) {
                res++;
                System.out.println(product);
            }
            for (int j = L; j < nums.length; j++) {
                product /= nums[j - L];
                product *= nums[j];
                if (product < k){
                    System.out.println(L + "--\t" + product);
                    res++;
                }
            }
        }
        return res;
    }
    /*官方思路*/
    //1.二分查找 使用对数
    public int numSubarrayProductLessThanK1(int[] nums, int k) {
        if (k == 0) return 0;
        double logk = Math.log(k);
        double[] prefix = new double[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            //loga + logb = logab
            prefix[i+1] = prefix[i] + Math.log(nums[i]);
        }

        int ans = 0;
        for (int i = 0; i < prefix.length; i++) {
            int lo = i + 1, hi = prefix.length;
            while (lo < hi) {
                int mi = lo + (hi - lo) / 2;
                if (prefix[mi] < prefix[i] + logk - 1e-9) lo = mi + 1;
                else hi = mi;
            }
            ans += lo - i - 1;
        }
        return ans;
    }
    //2.双指针
    public int numSubarrayProductLessThanK2(int[] nums, int k) {
        if (k <= 1) return 0;
        int prod = 1, ans = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            //如果大于等于目标值，左指针右移
            while (prod >= k) prod /= nums[left++];
            //累计个数
            ans += right - left + 1;
        }
        return ans;
    }
}
